package com.leo.leetcode.s100;

/**
 *
 * @author xuexiaolei
 * @version 2017年11月20日
 */
public class T20ValidParentheses {
    public static boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int pos=-1;
        for (int i = 0; i < s.length(); i++) {
            if (pos>-1 && isMatch(stack[pos],s.charAt(i))){
                pos--;
                continue;
            }
            stack[++pos] = s.charAt(i);
            if (pos > s.length()/2) return false;
        }
        if (pos==-1){
            return true;
        }else {
            return false;
        }
    }

    private static boolean isMatch(char c, char c1) {
        if (c=='{' && c1=='}') return true;
        if (c=='(' && c1==')') return true;
        if (c=='[' && c1==']') return true;
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isValid(""));
        System.out.println(isValid("({})"));
        System.out.println(isValid(")({})("));
        System.out.println(isValid("))(("));
    }
}
